#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <random>
#include "common/tree.h"
#include "sort.h"

int main() {
    /*
    BinaryTree<char> tree;

    node_<char>* proot;
    proot = new node_<char>('A');
    proot->lchild_ = new node_<char>('B');
    proot->rchild_ = new node_<char>('C');
    proot->lchild_->lchild_ = new node_<char>('D');
    proot->lchild_->rchild_ = new node_<char>('E');
    proot->rchild_->lchild_ = new node_<char>('F');
    proot->lchild_->lchild_->rchild_ = new node_<char>('G');
    tree.set_root_FOR_TEST(proot);

    tree.printInOrder(BinaryTree<char>::IN);
    tree.printInOrder(BinaryTree<char>::POST);
    tree.printInOrder(BinaryTree<char>::PRE);

    tree.thread(BinaryTree<char>::IN);
*/
    std::vector<int> list1(100);
    std::iota(list1.begin(), list1.end(), 0);
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(list1.begin(), list1.end(), g);

    for (auto e : list1)
        std::cout << e << " ";
    std::cout <<std::endl;
    //selection_sort(list1);
    //insertion_sort(list1);
    //shell_sort(list1, 30);

    std::vector<int> list3{9, 1, 3, 7, 5};
    //quick_sort(list1);
    quick_sort_3_way(list1);

    std::cout << std::endl;
    for (auto e : list1)
        std::cout << e << " ";

    return 0;
}
